/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.backtracking;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * <p>
 * 输出排列 元素有重复的排列情况 输入： [1,1,2] 输出: [1,1,2], [1,2,1], [2,1,1].
 * </p>
 * 
 * @author towan
 * @Email tongwenzide@163.com 2015年5月24日
 * @version V1.0
 */
public class PermutationsII {

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        if (nums == null) {
            return result;
        }
        // 对数列进行排序
        Arrays.sort(nums);

        // 递归方法
        List<Integer> path = new ArrayList<Integer>();
        boolean[] used = new boolean[nums.length];// 记录元素的使用情况
        findPermutations2(nums, used, path, result);

        return result;
    }

    /**
     * 查找有重复元素的数组的排列个数
     * 
     * @param nums
     * @param used
     * @param path
     * @param result
     * @author towan
     * @Email tongwenzide@163.com 2015年5月24日
     */
    private void findPermutations2(int[] nums, boolean[] used, List<Integer> path,
            List<List<Integer>> result) {
        if (nums.length == path.size()) {
            result.add(new ArrayList<Integer>(path));
        }
        for (int i = 0; i < nums.length; i++) {
            // 除了考虑当前使用情况外，还需要判断重复元素是否是第一个
            if (used[i] || (i > 0 && !used[i - 1] && nums[i] == nums[i - 1])) {
                continue;
            }
            // 加入新元素进行递归
            path.add(nums[i]);
            used[i] = true;
            
            findPermutations2(nums, used, path, result);
            
            // 回退
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
    public static void main(String[] args) {
        int []nums  = {1,1,2};
        System.out.println(new PermutationsII().permuteUnique(nums));
    }
}
